package 中等.找规律;

/**
 * 给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）
 * 并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。
 * 比方说，如果 nums = [6,1,7,4,1] ，那么：
 * 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
 * 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
 * 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。
 * 如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。
 * 请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ways-to-make-a-fair-array
 */
public class 生成平衡数组的方案数_1664 {

    public static void main(String[] args) {

        System.out.println(waysToMakeFair(new int[]{1, 1, 1}));

    }

    /**
     * 如果当前删除第 i 个数，那么前面的奇偶不变，后面的奇偶互换
     * 分类讨论：
     * 1，如果当前位置是奇数
     * 那么 i+1 的位置统计的是 偶数和，i+2 的位置统计的是 奇数和
     * 2，如果当前位置是偶数
     * 那么 i+1 的位置统计的是 奇数和，i+2 的位置统计的是 偶数和
     * 注意：计算的时候后面的奇偶进行互换计算
     */
    public static int waysToMakeFair(int[] nums) {
        int[] suffixOddSum = new int[nums.length];
        int[] suffixEvenSum = new int[nums.length];

        for (int i = nums.length - 1; i >= 0; i--) {
            if ((i + 1) % 2 == 0) {  // 偶数
                suffixEvenSum[i] = nums[i] + ((i + 2) < nums.length ? suffixEvenSum[i + 2] : 0);
            } else {
                suffixOddSum[i] = nums[i] + ((i + 2) < nums.length ? suffixOddSum[i + 2] : 0);
            }
        }

        int count = 0;
        int preOddSum = 0, preEvenSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((i + 1) % 2 == 0) {  // 偶数
                if (preEvenSum + ((i + 1) < nums.length ? suffixOddSum[i + 1] : 0) ==
                        preOddSum + ((i + 2) < nums.length ? suffixEvenSum[i + 2] : 0)) {
                    count++;
                }
                preEvenSum += nums[i];
            } else {
                if (preOddSum + ((i + 1) < nums.length ? suffixEvenSum[i + 1] : 0) ==
                        preEvenSum + ((i + 2) < nums.length ? suffixOddSum[i + 2] : 0)) {
                    count++;
                }
                preOddSum += nums[i];
            }
        }
        return count;
    }

}
